/*
 * Program HW 1 Compute Prefix Sum with MPI
 * Name: Songgang Xu
 * Email sxu@tamu.edu
 */

/*
 * prefix_sum.mpi.c - Description:
 * Compute prefix_sum using MPI
 * User specify the number of random integers and the number of processors
 * Show the time elapse display
 */ 

#include <stdlib.h>
#include <time.h>
#include <sys/resource.h>
#include <math.h>

/*
 * Generate Random Integers  */
void generateRandomIntegers (int * memory, int n) {

	int i;
	for (i=0; i<n; i++) 
	{
		memory[i] = rand();
	}

	return;

}
/*
 * printElapsed (calculate & print out time elapsed)
 */
void printElapsed (char *desc, struct timeval *start, struct timeval *end, int niters)
{
	struct timeval elapsed;
	if (start -> tv_usec > end -> tv_usec)
	{
		end -> tv_usec += 1000000;
		end -> tv_sec--;
	}

	elapsed.tv_usec = end -> tv_usec - start -> tv_usec;
	elapsed.tv_sec = end -> tv_sec - start -> tv_sec;

	printf("\n %s total elapsed time = %1d (usec)",
		   desc, (elapsed.tv_sec*1000000 + elapsed.tv_usec)/niters);

}/* printElapsed() */

int main(int argc, char ** argv)
{
	int numints;                           /* Number of integers */
	int * integers = NULL;                 /* Memory for the random integers */
	int * prefix_sum = NULL;               /* Memory for the prefix sum*/

	struct timeval tmstart, tmend;         /* record the start time and the end time of the algorithm */
	struct timeval genstart, genend;       /* record the start time and the end time of generation random integers */
	struct timezone tzp;                   /* used in gettimeofday */

	if (argc < 2)
	{
		printf ("Usage : %s [numints]\n", argv[0]);
		return 0;
	}

	numints = atoi(argv[1]);
	/*
	 * Allocate memory for integers
	 */
	integers = (int * ) malloc (sizeof (int) * numints);
	prefix_sum = (int * ) malloc (sizeof (int) * numints);

	if (! integers || ! prefix_sum)
	{
		printf ("\n Unable to malloc ()\n");
	}

	generateRandomIntegers (integers, numints);

	gettimeofday(&genstart, &tzp);

	/*
	 * Compute the prefix sum
	 */
	int sum = 0;
	int i = 0;
	for (i = 0; i < numints; ++i)
	{
		sum += integers[i];
		prefix_sum[i] = sum;
	}
	gettimeofday(&genend, &tzp);
	printElapsed("\n Prefix Sum Time  ", &genstart, &genend, 1);

	printf ("\n");
/*
	printf ("Numbers are :");
	for (i = 0; i < numints; ++i)
	{
		printf ("%d ", integers[i]);
	}
	printf ("\n");
    printf ("Prefix sums are :");
    for (i = 0; i < numints; ++i)
    {
        printf ("%d ", prefix_sum[i]);
    }
   	printf ("\n");
*/	
	return 0;
}
